DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2016.30

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

Authors: Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/k^{O(k)}) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2^{~O(n^{1-1/2^{k-1}})} and needs white box access only to know the order in which the variables appear in the ABP.

Cite as

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:LIPIcs.CCC.2016.30,
  author =	{Anderson, Matthew and Forbes, Michael A. and Saptharishi, Ramprasad and Shpilka, Amir and Volk, Ben Lee},
  title =	{{Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{30:1--30:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.30},
  URN =		{urn:nbn:de:0030-drops-58255},
  doi =		{10.4230/LIPIcs.CCC.2016.30},
  annote =	{Keywords: Algebraic Complexity, Lower Bounds, Derandomization, Polynomial Identity Testing}
}

Document

DOI: 10.4230/LIPIcs.STACS.2014.41

On Symmetric Circuits and Fixed-Point Logics

Authors: Matthew Anderson and Anuj Dawar

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract

We study properties of relational structures such as graphs that are decided by families of Boolean circuits. Circuits that decide such properties are necessarily invariant to permutations of the elements of the input structures. We focus on families of circuits that are symmetric, i.e., circuits whose invariance is witnessed by automorphisms of the circuit induced by the permutation of the input structure. We show that the expressive power of such families is closely tied to definability in logic. In particular, we show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixed-point logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits.

Cite as

Matthew Anderson and Anuj Dawar. On Symmetric Circuits and Fixed-Point Logics. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 41-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:LIPIcs.STACS.2014.41,
  author =	{Anderson, Matthew and Dawar, Anuj},
  title =	{{On Symmetric Circuits and Fixed-Point Logics}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{41--52},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.41},
  URN =		{urn:nbn:de:0030-drops-44455},
  doi =		{10.4230/LIPIcs.STACS.2014.41},
  annote =	{Keywords: symmetric circuit, fixed-point logic, majority, counting, uniformity}
}

Search Results

Documents authored by Anderson, Matthew

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

Abstract

Cite as

On Symmetric Circuits and Fixed-Point Logics

Abstract

Cite as

Thanks for your feedback!

Could not send message